package elementary_alg.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author : Kong Decheng
 * @date : 2021/04/02
 * @description: 两数之和
 */
public class LC9 {
    /**
     * 暴力求解
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] solution_1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 使用 hashmap
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] solution_2(int[] nums, int target) {
        // 将数组中的值全部放到字典里，值为 key, 索引为 value
        Map<Integer, Integer> map = new HashMap<>();
        // 遍历数组，求差，看字典里是否有差值
        for (int i = 0; i < nums.length; i++) {
            // 如果 map 里存在对应的差值，则返回索引
            if (map.get(target - nums[i]) != null) {
                return new int[]{map.get(target - nums[i]), i};
            }
            // 值为 key, 索引为 value
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}
